package homework;

import java.util.Stack;

//牛客JZ31、栈的压入、弹出序列（不可能的出栈顺序）（中等）
public class IsPopOrder {
    public static boolean IsPopOrder(int [] pushA,int [] popA) {
        //思路：一边存一边比较是否一样，不一样就弹出并且j++，然后一直比
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int j = 0;
        while (j < popA.length && i < pushA.length){
            stack.push(pushA[i]);
            while (!stack.empty() && stack.peek() == popA[j]){
                j++;
                stack.pop();
            }
            i++;
        }
        return stack.empty();
    }

    public static void main(String[] args) {
        int[] pushA = {1,2,3,4,5};
        int[] popA = {4,5,3,2,1};
        boolean flag = IsPopOrder(pushA, popA);
        System.out.println(flag);
    }
}
